CODE 6. Word Ladder II

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/19/2013-11-19-CODE 6 Word Ladder II/

访问原文「CODE 6. Word Ladder II」

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

public ArrayList<ArrayList<String>> findLadders(String start, String end,
			HashSet<String> dict) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (start.equals(end) || dict.size() == 2) {
			ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
			return results;
		}
		
		dict.add(start);
		dict.add(end);

		Map<String, DepthWordsPair> map = new HashMap<String, DepthWordsPair>();
		map.put(start, new DepthWordsPair(1));

		Queue<String> q = new LinkedList<String>();
		int depth = 1;
		int len = start.length(); // word length
		int min_depth = dict.size() + 2; // 2 for start and end words
		q.offer(start);

		while (!q.isEmpty() && min_depth > depth) {
			String cur = q.poll();

			depth = map.get(cur).getDepth();
			for (int i = 0; i < len; ++i) // check word(s)
			{
				StringBuilder sb = new StringBuilder(cur);
				for (char a = 'a'; a <= 'z'; ++a) {
					if (a == cur.charAt(i))
						continue;
					sb.setCharAt(i, a);
					String t = sb.toString();

					if (t.equals(end)) {
						min_depth = depth + 1;
					}

					if (dict.contains(t)) {
						DepthWordsPair dwp = map.get(t);
						if (null == dwp) {
							DepthWordsPair dw = new DepthWordsPair(depth + 1);
							dw.getWords().add(cur);
							map.put(t, dw);
							q.offer(t);
						} else if (dwp.getDepth() == depth + 1) {
							dwp.getWords().add(cur);
						}
					}
				}
			}
		} // end while

		ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
		if (min_depth == dict.size() + 2) { // only for start and end words
			return result;
		}
		Stack<String> stack = new Stack<String>();
		Stack<String> sequence = new Stack<String>();
		stack.push(end);
		while (!stack.isEmpty()) {
			String top = stack.pop();
			sequence.push(top);
			List<String> sons = map.get(top).getWords();
			for (int i = 0; i < sons.size(); ++i) {
				stack.push(sons.get(i));
			}
			if (sons.size() == 0) {
				int index = result.size();
				result.add(new ArrayList<String>());
				for (int i = sequence.size() - 1; i >= 0; --i) {
					result.get(index).add(sequence.get(i)); // save result
				}
				top = sequence.pop();
				while (!sequence.empty()) {
					String father = sequence.peek();
					List<String> brothers = map.get(father).getWords();
					if (!top.equals(brothers.get(0))) {
						break;
					}
					sequence.pop();
					top = father;
				}
			}
		}
		return result;

	}

	class DepthWordsPair {
		int depth;
		List<String> words;

		public DepthWordsPair(int depth) {
			this.depth = depth;
			words = new ArrayList<String>();
		}

		public int getDepth() {
			return depth;
		}

		public void setDepth(int depth) {
			this.depth = depth;
		}

		public List<String> getWords() {
			return words;
		}

		public void setWords(List<String> words) {
			this.words = words;
		}
	}